#pragma once

#include <algorithm>  // std::make_heap / std::push_heap / std::pop_heap
#include <cstddef>    // std::size_t
#include <vector>     // std::vector

namespace heapmerge {

/**
 * @brief 表示单个已排序 run 的读指针，用于堆归并过程。
 *
 * @tparam Record    run 中元素的数据类型。
 * @tparam Container run 的容器类型（默认 std::vector<Record>）。
 *
 * @details
 *  - 用指针指向外部的已排序容器，避免复制数据；
 *  - 通过 index 维护当前读取位置；
 *  - value 用于保存最近一次读取的元素，以支持堆比较；
 *  - operator< 采用反向比较以在 std::make_heap 构建的 max-heap 上模拟最小堆语义。
 */
template <typename Record, typename Container = std::vector<Record>>
struct Input {
    const Container* file = nullptr; ///< 指向某个已排序 run（外部数据所有权由调用方管理）。
    std::size_t index = 0;           ///< 当前读取位置（游标）。
    Record value{};                  ///< 最近一次读取的元素值（堆顶比较使用）。

    explicit Input(const Container* f) : file(f), index(0) {}

    /**
     * @brief 从 run 中读取下一条记录。
     *
     * @return 若成功读取则返回 true；若到达末尾或 file 为空则返回 false。
     */
    bool next() {
        if (!file || index >= file->size()) {
            return false; // run 已读尽或未初始化
        }
        value = (*file)[index++];    // 取出当前值并推进索引
        return true;
    }

    /**
     * @brief 重载小于比较，实现在默认 max-heap 上构造 min-heap。
     *
     * @note C++ 标准库的堆算法默认使用最大堆，因此这里取反比较。
     */
    bool operator<(const Input& rhs) const {
        return value > rhs.value;    // 反向比较：值越小优先级越高
    }
};

/**
 * @brief 对多路已排序 run 进行归并，生成新的有序容器。
 *
 * @tparam Container run 的容器类型（需支持随机访问迭代器和 push_back）。
 * @param runs      输入的已排序 run 列表。
 * @return 合并后的有序容器。
 *
 * @details
 *  - 使用大小为 runs.size() 的最小堆维护每个 run 当前最小元素；
 *  - 每次弹出堆顶元素追加到 output 中，同时从对应 run 读取下一条记录；
 *  - 若所有 run 都为空，则返回空容器；
 *  - 算法时间复杂度 O(N log K)，其中 N 为所有元素数量，K 为 run 个数。
 */
template <typename Container>
Container merge_runs(const std::vector<Container>& runs) {
    using Record = typename Container::value_type;

    Container output;                                    // 存放归并结果
    std::vector<Input<Record, Container>> heap;          // 最小堆
    heap.reserve(runs.size());                           // 预留空间减少扩容次数

    for (const auto& run : runs) {                       // 初始化：每个 run 提取首元素
        Input<Record, Container> in(&run);
        if (in.next()) {
            heap.push_back(in);                          // 只有非空 run 才入堆
        }
    }

    if (heap.empty()) {                                  // 所有 run 均为空
        return output;
    }

    std::make_heap(heap.begin(), heap.end());            // 建堆（依据 Input::operator<）

    while (!heap.empty()) {                              // 循环直至所有 run 耗尽
        std::pop_heap(heap.begin(), heap.end());         // 将最小元素移至末尾
        auto current = heap.back();                      // 取出堆尾（当前最小值）
        heap.pop_back();

        output.push_back(current.value);                 // 写入归并结果

        if (current.next()) {                            // 尝试读取该 run 的下一元素
            heap.push_back(current);                     // 仍有数据则重新入堆
            std::push_heap(heap.begin(), heap.end());    // 调整堆结构维持最小堆
        }
    }
    return output;
}

} // namespace heapmerge